package Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:利用数组模拟实现循环队列
 * User: 阿宾
 * Date: 2024-11-14
 * Time: 14:23
 */

//注意：本方法是浪费一个内存空间
public class MyCircularQueue {

    private int[] elem;
    int maxSize;//创建的数组空间大小

    int first;//指向队列首元素，指向的位置是要出队的位置
    int last;//指向队列尾，指向的位置是要插入的位置

    public MyCircularQueue(int k) {
        this.maxSize = k+1;//关键点
        this.elem = new int[maxSize];
        this.first = 0;
        this.last = 0;
    }

    /**
     * 向循环队列插入一个元素。如果成功插入则返回真。
     * @param value
     * @return
     */
    public boolean enQueue(int value) {
        //1.先判断队列是否满
        if(!isFull()){
            //2.插入元素
            elem[last] = value;
            //3.更新last
            last = (last + 1) % maxSize;
            return true;
        }
        //队满返回false
        return false;

    }

    /**
     * 从循环队列中删除一个元素。如果成功删除则返回真。
     * @return
     */
    public boolean deQueue() {
        //1.判断是否为空
        if(!isEmpty()){
            //删除不是真正把数据删除，而是逻辑删除，这样插入的时候是直接将数据覆盖
            //更新first值
            first = (first + 1) % maxSize;
            return true;
        }
        //队列为空返回false
        return false;

    }

    /**
     * 从队首获取元素。如果队列为空，返回 -1 。
     * @return
     */
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return elem[first];
    }

    /**
     * 获取队尾元素。如果队列为空，返回 -1 。
     * @return
     */
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        /*
        因为last指向的位置是要插入的位置，所以队尾元素是last上一个元素,即last-1位置
        _      _      _    5    6
        last             first
        但是防止发生要插入位置是下标为0位置，也就是上述情况，所以不能直接写last-1,而是要修改
         */
        int index = (last + maxSize -1) % maxSize;
        return elem[index];
    }

    /**
     * 检查循环队列是否为空。
     * @return
     */
    public boolean isEmpty() {
        if(first == last){
            return true;
        }
        return false;
    }

    /**
     * 检查循环队列是否已满。
     * @return
     */
    public boolean isFull() {
        if((last + 1) % maxSize == first){
            return true;
        }
        return false;
    }
}
